// WordConvert.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "string.h"

/*
Edit Distance. Given two text strings A of length n and B of length m, 
you want to transform A into B with a minimum number of operations of 
the following types: delete a character from A, insert a character into A, 
or change some character in A into a new character. The minimal number of 
such operations required to transform A into B is called the edit distance between A and B. 

In the code, input string Source[1...i], Destination[1...j]
Costs for add to source: COST_ADD
Costs for delete from source: COST_DELETE
Costs for Replace source: COST_REPLACE
P[i][j] means the cost to convert string source with length i to destination string with length j

the solution is at item 8 on page http://people.csail.mit.edu/bdean/6.046/dp/ 
*/

#define INT_MAX		0x7fffffff
#define MAX_WORD_LENGTH	20
#define COST_ADD		1
#define COST_DELETE		1
#define COST_REPLACE	1
#define MIN(x, y)	(x>y?y:x)
#define MAX(x, y)	(x>y?x:y)

int P[MAX_WORD_LENGTH+1][MAX_WORD_LENGTH+1] = {0};

int Convert( char* Source, char* Destination)
{
	int sLength = strlen(Source);
	int dLength = strlen(Destination);
	int i,j;

	//
	// Initialize the array
	//
	for( i=0; i<=sLength; i++ )
	{
		for( j=0;j<=dLength; j++)
		{
			P[i][j] = INT_MAX; 
		}
	}

	//
	// to convert any character to null, delete characters from source
	//
	P[0][0] = 0;
	for( i =1; i<=sLength; i++)
	{
		P[i][0] = P[i-1][0]+COST_DELETE;
	}

	//
	// to convert the null to be any char, add characters to source
	//
	for( i=1; i<=dLength; i++)
	{
		P[0][i] = P[0][i-1]+COST_ADD;
	}

	for( i=1; i<=sLength; i++ )
	{
		for( j=1;j<=dLength; j++)
		{
			P[i][j] = MIN(P[i][j-1]+COST_ADD, P[i-1][j]+COST_DELETE);
			if( *(Source+i-1) == *(Destination+j-1) )
			{
				P[i][j] = MIN( P[i][j], P[i-1][j-1]);
			}
			else
			{
				P[i][j] = MIN( P[i][j], P[i-1][j-1]+COST_REPLACE);
			}
		}
	}

	for( i=1; i<=sLength; i++ )
	{
		for( j=1;j<=dLength; j++)
		{
			printf("%d  ",P[i][j]); 
		}
		printf("\n");
	}
	return P[sLength][dLength];
}

int _tmain(int argc, _TCHAR* argv[])
{
	char *source = "source";
	char* destination = "destination";

	int minSteps = Convert( source, destination);	
	printf("the mininum steps to convert %s to %s is %d\n", source, destination, minSteps);
	
	return getchar();
}

